package com.itzmn.datastructure.sort;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/9 11:18
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 快速排序
 *
 *  思路：
 *  选择一个基准数，将小于基准数的放在左边，将大于基准数的放在右边，通过递归，分别计算两边。
 *             第一个数为基准数，从右向左查找比基准数小的数，和基准数调换位置，
 *             从左往右查找比基准数大的数，和刚刚调换的大数调换位置，直到结束，将基准数放在中间位置。
 *             就完成一次循环，
 *             知道两个索引相遇，然后分别排列两边的两个
 *
 *  0， 5
 *  1,6,3,7,7,6
 */
public class QKSort {

    public static void main(String[] args) {
        int[] ints = {2,5,4,6,3,7,1};

        new QKSort().qkSort(ints,0,ints.length-1);
    }
    /**
     * 快速排序，将传入的数组进行排序，从右至左查找比基准数小的，从左至右查找比基准数大的，然后交换位置
     * @param arrs
     * @param start 数组的开始位置
     * @param end  数组的结束位置
     */
    public void qkSort(int arrs[],int start,int end){

        if (end <= start){
            return;
        }
        //默认第一个值为基准数
        int tem = arrs[start];
        //记录下开始的坐标
        int left = start;
        int right = end;

        //开始比较，两个位置不可以相等
        while (end != start){
            //如果右边的比基数大，坐标就一直递减，直到小于，或者达到和左边的位置一样
            while (arrs[end]>=tem && start<end){
                --end;
            }
            //如果找到了右边比基数小的，将小的值赋给基数的位置，
            arrs[start] = arrs[end];

            //然后从左至右扫描，如果左边比基数小，坐标就增加，直到找到比基数大的，或者坐标相等
            while (arrs[start]<=tem && start<end){
                ++start;
            }
            //将左边这个大的，放在右边的那个大的位置
            arrs[end] = arrs[start];
        }
        //将基准数放在中间位置
        arrs[start] = tem;
        log(arrs);
        qkSort(arrs,left,start-1);
        qkSort(arrs,start+1,right);

    }

    public void log(int arrs[]){

        for (int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+" ");
        }
        System.out.println();
    }



}
